เมนูนำทาง
เอ็นพี (ความซับซ้อน) ทำไมบางปัญหาในเอ็นพีจึงยากเนื่องจากว่าปัญหาที่อยู่ในกลุ่มนี้หลายอย่างมีประโยชน์เป็นอย่างมากในการแก้ปัญหาในชีวิตจริง นักวิจัยหลายคนจึงพยายามที่จะหาขั้นตอนวิธีที่มีประสิทธิภาพ (ทำงานในเวลาที่เป็นพหุนามกับขนาดของอินพุต) ในการแก้ปัญหาเหล่านี้ แต่ว่า จนกระทั่งปัจจุบัน ปํญหาหลายอย่างยังไม่สามารถหาขั้นตอนวิธีที่มีประสิทธิภาพได้
กลุ่มของปัญหาที่สำคัญเป็นอย่างมากในกลุ่มของเอ็นพีก็คือ เอ็นพีบริบูรณ์ ซึ่งมักจะถูกเรียกว่าเป็นกลุ่มของปํญหาที่ยากที่สุดในเอ็นพี เนื่องมาจากว่า การแก้ปัญหาเอ็นพีบริบูรณ์ได้อย่างมีประสิทธิภาพ ส่งผลให้เราสามารถแก้ปัญหาทั้งหมดในกลุ่มของเอ็นพีได้อย่างมีประสิทธิภาพด้วย ในปัจจุบัน หากปัญหาใดถูกจัดอยู่ในกลุ่ม เอ็นพีบริบูรณ์ นักวิจัยจะเลิกล้มความคิดที่จะหาคำตอบของปํญหานั้น (อย่างมีประสิทธิภาพ) ทันที โดยมักเปลี่ยนเป้าหมายไปที่การหาขั้นตอนวิธีแบบประมาณแทน
เราจะมาดูตัวอย่างของปัญหาปัญหาหนึ่งที่มีความก้าวหน้าอย่างสม่ำเสมอในเชิงของการหาอัลกอริธึมที่มีประสิทธิภาพสำหรับปัญหานั้น ปัญหานี้ก็คือปัญหา "จำนวนเฉพาะ (PRIME) " ซึ่งปัญหานี้ก็คือ
กำหนดจำนวนจำนวนหนึ่งมาให้ในรูปแบบของเลขฐานสอง ให้ตัดสินว่าจำนวนนี้เป็นจำนวนเฉพาะหรือไม่จะเห็นว่าการจัดปัญหานี้เข้าไปใน โค-เอ็นพี ค่อนข้างจะง่ายและชัดเจน แต่หลังจากนั้นนักวิจัยต้องใช้ความพยายามอย่างมากในการจัดปัญหานี้เข้าไปใน เอ็นพี อาร์พี และ พี ตามลำดับ
เมนูนำทาง
เอ็นพี (ความซับซ้อน) ทำไมบางปัญหาในเอ็นพีจึงยากใกล้เคียง
แหล่งที่มา
WikiPedia: เอ็นพี (ความซับซ้อน) http://qwiki.caltech.edu/wiki/Complexity_Zoo#np